Printing systems with an ability to generate multilevel printed single dots increase the number of gray levels that can be achieved compared to binary systems. Multilevel halftoning mechanisms based on error diffusion are used to render an image on a device with a number of levels greater than two. Multilevel error diffusion algorithms generate a dot distribution with high frequency noise (“blue noise”) and visually pleasant dot patterns. Error diffusion algorithms, which typically provides better image quality compared to other blue noise dither algorithms were widely investigated and used because they can be easily embedded into a processor for real time purposes.
A two-dimensional multilevel “error diffusion” algorithm is an adaptive algorithm that uses threshold weighted error feedback to produce patterns with different spatial frequency content, depending on the input image values. The process, shown schematically in FIG. 2, consists of single pass over the input image. Each pixel with a continuous tone value 220 (SYSVAL01) is first modified by adding a previously calculated weighted error to generate value 224 (SYSVAL02). Value 224 is entered into threshold computing component 204 to generate an output value 228 (SYSVAL03) by comparing to value 224 to first threshold value 304 (THR01), as indicated by the meta program shown FIG. 4. The output value 228 is a quantization value that can get one of first quantization value 308 (QUANT01) or last quantization value 312 (QUANT02), in a two level system. For example, FIG. 3 shows that for an 8-bits contone image, the first threshold value 304 may be set to 127 wherein the quantization values 308 and 312 are respectively 0 and 255. Related to a printing device, first quantization value 308 can be defined as a printer dot OFF (no dot on the paper) and last quantization value 312 will be set as dot ON. The difference between the output value 228 and the modified input value 224 is computed to generate error 212. Error 212 is entered into the weighted error feedback component 208 to generate weighted error value 216. Weighted error value 216 is passed to the neighboring pixels that have not been processed yet as shown in FIG. 2, using an error distribution matrix shown in FIG. 5. Error diffusion kernel matrix 504 may be constructed by 12 coefficients, which are defined geometrically and are ordered into three lines in this case. In general these coefficients are normalized such that their total sum equals to 1.
A multilevel error diffusion algorithm is a natural generalization of the two levels error diffusion algorithm for multilevel system. Multilevel system means that there is a control of printer dot size or drop volume in term of the amount of ink per dot type. In this case threshold computing component 204 is replaced by a multilevel quantization component 604 as is shown in FIG. 6. In this example, for a four levels system, the modified input value 224 of a pixel is compared to first threshold value 304 (THR01), second threshold value 704 (THR02), and third threshold value 708 (THR03) as is shown in FIG. 7 and in FIG. 8, to create one of four quantization system values, first quantization value 308 (QUANT01), third quantization value 712 (QUANT02), fourth quantization value 716 (QUANT03), and last quantization value 312 (QUANT04).
One of the draw backs of multilevel error diffusion algorithm is the textures artifacts 104 such as “worm pattern” (discussed below), and discontinuity and contouring around quantization levels (See FIG. 1B). Sugiura and Makita (An Improved Multilevel Error Diffusion Method; The Journal of Imaging Science and Technology, 1995, Vol. 39, No. 6, pp. 495-501) explained that this effect appears when no error occurs at quantization levels. For the same reason, for binary system, “worm” pattern and discontinuity appear at highlight and shadow tones. Solutions were proposed to smooth highlight and shadow tones for binary systems. Some of them proposed to add noise to the input pixels value such as Masake and Hiroaki (Modified Error Diffusion with Smoothly Disperse Dots in Highlight and Shadow; Japan Hardcopy '98, 1998, pp. 379-382). In the Raph Levien paper (Output Dependent Feedback in Error Diffusion Halftoning; IS&T 46th Annual Conference, May 1993, pp. 115-118); and U.S. Pat. No. 5,917,614 (Levien), it was proposed to break highlight and shadow patterns, by applying modulation to the error diffusion threshold term. The modulation is based on a difference between an “actual distance” and between a “predefined expected” distance. This distance is defined as the distance between actual pixel (pixel being considered), to the closest turned on pixel. The “predefined expected” distance is a function of the input pixel value. Levien addresses shortly the problem of multilevel error diffusion in an additional paper, Practical Issues in Color Inkjet Halftoning; IS&T Electronic Imaging, SPIE Vol. 5008, 1993, pp. 537-541, wherein a modulation of the threshold value is again proposed based on the distance parameter previously described.
For multilevel system, Sugiura and Makita proposed to smooth the quantization transition by applying noise to the input pixels. U.S. Pat. No. 6,271,936 (Yu et al.) and U.S. Publication No. 2005/0195438 (Couwenhoven et al.) proposed to combine error diffusion techniques with dithering techniques based on periodical threshold array.
The present invention is directed towards improving transition smoothness at quantization values by controlling the density and position of quantized dots value around quantization area, and keeping the pleasant dot distribution of error diffusion.